package main

import (
	"fmt"
)

func generateParenthesis(n int) []string {
	if n == 0 {
		return []string{}
	}
	var ans []string
	var dfs func(leftCount, n int, res string)

	dfs = func(leftCount, n int, res string) {
		if len(res) == n {
			ans = append(ans, res)
			return
		}
		if leftCount > 0 {
			// 左括号的数量大于0 可以补)
			dfs(leftCount-1, n, res+")")
		}
		if n-len(res) > leftCount {
			// 剩余的大于左括号的数量可以补(
			dfs(leftCount+1, n, res+"(")
		}
	}

	dfs(0, n*2, "")
	return ans
}

func main() {
	fmt.Println(generateParenthesis(3))
}
